package backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/25 16:48
 * https://leetcode-cn.com/problems/combination-sum-iii/
 *组合总和 III
 */
public class CombinationSum3 {

    static List<List<Integer>> result;
    static LinkedList<Integer> list;

    /**
     * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
     * @param k
     * @param n
     * @return
     */
    public static List<List<Integer>> combinationSum3(int k, int n) {
        result = new ArrayList<>();
        list = new LinkedList<>();
        traversal(k, n, 1);
        return result;
    }

    public static void traversal(int k, int n, int cur) {
        if (k != 1 && list.size() == k - 1) {
            Integer poll = list.getLast();
            if (n > poll && n <= 9) {
                list.add(n);
                result.add(new ArrayList<>(list));
                list.removeLast();
            }
            return;
        }
        for (int i = cur; i <= 9 - (k - list.size()) + 1; i++) {
            list.add(i);
            n -= i;
            traversal(k, n, i + 1);
            list.removeLast();
            n += i;
        }
    }

    public static void main(String[] args) {
        combinationSum3(3, 9);
    }
}
